package 华为OD机试真题2023.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class HJ32_狼羊过河 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/32.txt"));
        MyUtil.START();
        Solution(in);
        MyUtil.END();
    }

    static int duianYang = 0, duianLang = 0, X = 0;
    static int min = Integer.MAX_VALUE;

    static LinkedList<Integer[]> tmpCelue = new LinkedList<>();
    static LinkedList<Integer[]> bestCelue = new LinkedList<>();

    static void Solution(Scanner in) {
        int M = in.nextInt();
        int N = in.nextInt();
        X = in.nextInt();
        dfs(M, N, 0);
        System.out.println(min);
        System.out.println(Arrays.deepToString(bestCelue.toArray()));
    }

    // 穷举法 两层循环遍历所有羊、狼，然后判断合理性
    static void dfs(int yang, int lang, int count) {
        if (yang == 0 && lang == 0) {
            //            min = Math.min(min, count);
            if (count < min) {
                min = count;
                bestCelue.clear();
                bestCelue.addAll(tmpCelue);
            }
        }
        if (count != 0) {
            if (lang >= yang || (duianYang != 0 && duianLang >= duianYang)) {
                return;
            }
        }
        for (int i = 0; i <= yang; i++) {
            if (i > X) {
                return;
            }
            for (int j = 0; j <= lang; j++) {
                if (i + j > X) {
                    break;
                }
                if (i + j == 0) {
                    continue;
                }
                duianYang += i;
                duianLang += j;
                tmpCelue.add(new Integer[] {i, j});
                dfs(yang - i, lang - j, count + 1);
                tmpCelue.removeLast();
                duianYang -= i;
                duianLang -= j;
            }
        }
    }
}
